The present invention relates to punctured codes and, more particularly, to methods and devices for efficient decoding of punctured codewords.
A common conventional error control strategy, on time-varying channels, is to adapt the rate according to available channel state information (CSI), which is called rate adaptability. An effective way to realize this coding strategy is to use a single code and to puncture the code in a rate-compatible fashion, a so-called rate-compatible punctured code (RCPC). In such an approach, the transmitter systematically punctures parity bits in a codeword, and the locations of the punctured symbols are known to the receiver/receivers. Since the decoder for the lowest rate (the base code) is compatible with the decoders for the other higher rates, RCPC needs no additional complexity for the rate adaptability. Moreover, RCPC permits one to transmit redundancies progressively in conjunction with automatic repeat request (ARQ)
Consider a linear block code defined by a generator matrix Γ. To encode an information vector b, Γ is right-multiplied by b to produce a codeword vector c:c=bΓ  (1)Associated with Γ are one or more parity check matrices H that satisfy the matrix equationHc=0  (2)for all the codeword vectors c of the code, i.e. a vector c belongs to the code if the vector satisfies equation (2). Typically, Γ, H and c are defined over the field GF(2), i.e. the elements of Γ, H and c are 0 or 1, and the addition of field elements is done as integer addition modulo 2.
In many cases, such as when Rate-Compatible Punctured Codes (RCPC) are being implemented, only a portion of the bits of the codeword c are transmitted over the channel, (in a communications scenario), or stored in a memory device, (storage applications). The locations of the transmitted bits are assumed to be known to both the transmitter and receiver, (of the communication system or storage device). Denote the transmitted or stored bits by c′ and refer to c′ as a sub-codeword. c′ also is referred to herein as a “punctured codeword”. The bits of c that are excluded from c′ are referred to herein as “punctured bits”. The bits received by the communications receiver, (or read by the memory reading device), typically are a noisy version of c′ that is referred to herein as a “representation” of c′, but by reuse of notation the received sub-codeword will still be denoted by c′.
The conventional method for decoding of c, given the representation of the sub-codeword c′, is by treating the punctured bits of c as “erasures”: during decoding, bits are inserted into c′ to bring the number of bits of c′ back up to the full number of bits of c, and then decoding is performed by decoding the code of the original matrix equation (2) while assigning special values (“erasures”) to the inserted bits. This procedure for decoding punctured codewords is referred to herein as “erasure decoding”.
To provide a concrete example of erasure decoding, Low-Density Parity Check (LDPC) codes now will be described.
A LDPC code is a linear binary block code whose parity-check matrix or matrices H is/are sparse. As shown in FIG. 1, a LDPC parity check matrix H is equivalent to a sparse bipartite “Tanner graph” G=(V,C,E) with a set V of N bit nodes (N=13 in FIG. 1), a set C of M check nodes (M=10 in FIG. 1) and a set E of edges (E=38 in FIG. 1) connecting bit nodes to check nodes. The bit nodes correspond to the codeword bits and the check nodes correspond to parity-check constraints on the bits. A bit node is connected by edges to the check nodes that the bit node participates with. In the matrix representation (matrix H of equation (2)) of the code on the left side of FIG. 1 an edge connecting bit node i with check node j is depicted by a non-zero matrix element at the intersection of row j and column i.
Next to the first and last check nodes of FIG. 1 are shown the equivalent rows of equation (1). The symbol “⊕” means “XOR”.
LDPC codes can be decoded using iterative message passing decoding algorithms. These algorithms operate by exchanging messages between bit nodes and check nodes along the edges of the underlying bipartite graph that represents the code. The decoder is provided with initial estimates of the codeword bits (based on the communication channel output or based on the read memory content). These initial estimates are refined and improved by imposing the parity-check constraints that the bits should satisfy as a valid codeword (according to equation (2)). This is done by exchanging information between the bit nodes representing the codeword bits and the check nodes representing parity-check constraints on the codeword bits, using the messages that are passed along the graph edges.
In iterative decoding algorithms, it is common to utilize “soft” bit estimations, which convey both the bit estimations and the reliabilities of the bit estimations.
The bit estimations conveyed by the messages passed along the graph edges can be expressed in various forms. A common measure for expressing a “soft” estimation of a bit v is as a Log-Likelihood Ratio (LLR)
      log    ⁢                  Pr        ⁡                  (                      v            =                          0              |                              current                ⁢                                                                  ⁢                constraints                ⁢                                                                  ⁢                and                ⁢                                                                  ⁢                observations                                              )                            Pr        ⁡                  (                      v            =                          1              |                              current                ⁢                                                                  ⁢                constraints                ⁢                                                                  ⁢                and                ⁢                                                                  ⁢                observations                                              )                      ,where the “current constraints and observations” are the various parity-check constraints taken into account in computing the message at hand and observations, such as the sequence of symbols received from a communication channel, corresponding to the bits participating in these parity checks. The sign of the LLR provides the bit estimation (i.e., positive LLR corresponds to v=0 and negative LLR corresponds to v=1). The magnitude of the LLR provides the reliability of the estimation (i.e., |LLR|=0 means that the estimation is completely unreliable and |LLR|=±∞ means that the estimation is completely reliable and the bit value is known).
Returning now to the discussion of decoding a punctured codeword by “erasure decoding”, if H is the parity-check matrix of an LDPC code, then the decoding is performed according to the Tanner graph associated with H, while assigning LLR=0 as an initial LLR to all the bits of the codeword c which are not bits of the sub-codeword c′ (i.e., to all the punctured bits of c).
Such erasure decoding may also be applied to other types of codes such as BCH codes.
In general, “erasure decoding” is more complex, and converges slower than, ordinary decoding. Moreover, typically the code is a systematic code, that encodes the input data bits as the codeword c by appending redundancy bits to the data bits, and the punctured bits are selected from among the redundancy bits, thus there is no real need to decode the punctured bits. A method that directly decodes the sub-codeword c′ and extracts the information bits, (which are typically the same as the information bits of c), would be of a significant benefit.